1. Field of the Invention
This invention relates to a one-time signature authentication scheme for wireless communications and, more particularly, to a flexible authentication scheme for authenticating messages sent wirelessly between vehicles that is a combination of a Winternitz one-time signature scheme and a hash to obtain random subset one-time signature scheme that provides a trade-off between communication and computational overhead.
2. Discussion of the Related Art
Vehicle-to-vehicle (V2V) wireless communications have been proposed for improved automobile safety. Under these applications, vehicles broadcast information over the wireless medium to one another. V2V applications aim to assist drivers in avoiding accidents by providing early warnings and advisories about potentially dangerous situations using the messages exchanged over the wireless medium. Vehicle-to-vehicle safety applications, such as blind spot warning (BSW) systems and cooperative collision warning (CCW) systems, rely on periodic V2V communications, such as the wireless dedicated short range communications (DSRC) standard. The advisories include road condition notification, co-operative collision warning, and so on. Security is critical in V2V driver assistance applications since drivers of vehicles are expected to make driving maneuvers based on the advisories they receive.
The wireless messages are typically transmitted at 10 Hz per vehicle, and are typically authenticated using digital signatures based on an underlying public key infrastructure (PKI) in accordance with the IEEE 1609.2 standard specification. Each principal in a PKI system has a pair of keys, namely a private key and a public key. The private key is known only to the principal and the public key can be shared with other entities in the system. The keys can be visualized as a pair of functions Pr and Pu representing the private and public keys, respectively, and having the property M=Pr(Pu(M)) and M=Pu(Pr(M)), where M is the message that is to be secured using the keys. To ensure message integrity, the sender of the message signs the message with his private key, and adds the signature to the message. Upon receiving the message, the recipient can verify the signature of the message using the sender's public key.
Although the discussion herein pertains to V2V networking, the various broadcast authentication techniques have a much wider application. At an abstract level, the various broadcast authentication techniques discussed herein apply to communication networks where nodes broadcast information to one another in an authentic manner. In these networks, potentially every node is a sender and a receiver. Thus, a given node would broadcast its packets to multiple nodes, and it may also receive packets from multiple, and possibly different, nodes. It is desirable to conserve bandwidth in these types of communication networks. Bandwidth is consumed when the public key is sent ahead of the messages or packets. Additional bandwidth is also consumed when signatures are appended to messages or packets. It is also desirable to conserve the use of the vehicle computer or CPU for verifying received messages. If all nodes send messages at some rate, then a vehicle might receive many more messages as compared to how many it sends. Thus, generally, when computational overhead is referred to, the time taken for key generation and signature generation is ignored, and the process focuses only on the time taken for signature verification.
Providing security in V2V driver assistance applications amounts to ensuring authenticity and integrity of the messages transmitted over the air. In other words, security in the sense of broadcast authentication. There are a number of challenges in providing security for V2V communications for the aforementioned driver assistance applications. The challenges include (i) resource constrained computing platforms, (ii) real-time latency requirements on the V2V messages, (iii) scarce communication bandwidth, and (iv) possibly rapid changes in the network topology. Such demands require the various algorithms to achieve security to impose minimal computations and communication overheads.
For the communications networks being discussed herein, the nodes would typically use an authentication protocol to achieve broadcast authenticity of the messages. An authentication protocol between a sender and a receiver enables the sender to send information to the receiver in an authentic manner. The authentication protocol used in the broadcast networks being discussed includes three steps, namely, key generation and public key distribution, signature generation and signature verification. For key generation and public key distribution, the sender executes a key generation algorithm for the authentication protocol and creates the public key, the private key and other variables. The sender then disseminates the public key to the receivers.
For signature generation, when the sender needs to send an authentic message, the sender creates the message and populates it with the appropriate information, and then uses a signature generation algorithm for the authentication protocol. In the case of digital signature algorithms, one public-private key pair can be used to sign a theoretically unlimited number of messages. In the case of one-time signature algorithms, as the name suggests, one public-private key pair can be used to sign only one message. Thus, in order to sign a message using a one-time signature, the sender needs to use the key generation algorithm and distribute the public key ahead of time. The signature generation algorithm generally uses the hash-and-sign paradigm. This means that the message is first hashed into a constant length string of bits. The hashed version, also called the message digest, is then signed using the signature generation algorithm.
For signature verification, when a receiver needs to verify the authenticity of a received message, it needs to have in its possession the public key corresponding to the private key that signed the message. Assuming that the receiver does not have the public key, it uses the signature verification algorithm for the authentication protocol. The verification algorithm also first hashes the message to derive the message digest, which is then subject to further verification steps.
The problem of broadcast authentication has been well-studied in the literature. However, there is no existing scheme that achieves all of the desired properties. For example, digital signatures achieve broadcast authentication with a reasonable communication overhead, such as elliptic curve digital signature algorithm (ECDSA). However, they are computationally quite intensive. One-time signature (OTS) schemes are a computationally efficient alternative, albeit at the expense of increased communication overhead.
ECDSA is a digital signature algorithm that can be used to sign a theoretically unlimited number of messages with a given public-private key pair. It is very bandwidth efficient since it has a small public key size and signature size. However, it is extremely computational intensive. A single hash operation, which is the building block of one-time signature algorithms, is four-five orders of magnitude quicker to execute on a generic processor as compared to an ECDSA signature generation or verification. For specialized hardware, the difference may even be higher.
A hash to obtain random subset (HORS) is a one-time signature algorithm that is generally used to sign only one message with a given public-private key pair. It may be used to sign multiple messages, but the security degrades rapidly. HORS is designed to be a fast authentication scheme, so it is extremely efficient computationally since it involves just a few hash operations. However, its bandwidth overhead is quite overwhelming, its signature size is moderate, but its public key size is extremely large, i.e., six-seven orders of magnitude higher than ECDSA.
The known Winternitz one-time signature scheme can only be used to sign one message for a given public-private key pair. It is designed to be bandwidth efficient, and its signature size is moderate and its public key size is smaller than even ECDSA. Further, its computational overhead is still one-two orders of magnitude smaller than that of ECDSA.
OTS schemes are typically constructed using the basic building blocks of a one-way hash function. One-way hash functions are functions that are easy to compute, but computationally infeasible to invert. The security of the OTS scheme depends on the security of the underlying one-way hash function. In general, OTS schemes are constructed using the following general methodology. A set of private values (often known as seals) is selected randomly. This serves as the private key. A set of public keys (often known as verifiers) is them computed by applying a one-way hash function on the private keys. The set of public keys is transmitted authentically to all receivers. When signing a message, the message is mapped to a subset of private key values, and that subset is released as a signature. Usually, the one-way hash function that is used in the OTS scheme is public. The receiver performs a sequence of one-way hash function computations that would transform the released signature values into some of the public key values which were authentically communicated earlier. The security of the signature lies in the fact that to forge a signature, the attacker has to perform at least one inversion of the underlying one-way hash function. These steps are shown below.                1. Select a one-way hash function, say, H: {0,1}*→{0,1}L.        2. Randomly choose a set of private values each of length L.        3. Generate one or a set of public values applying H(.) on the private values.        4. The set of private values act as private/signing key.        5. The set of public values act as public/verification key.        6. Map the message to be signed to the sub-set of private keys.        7. Release the sub-set of private keys obtained in step 6 as a signature.        